package com.swjd.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器
 *
 * @author 刘涛
 * @create 2021/9/25 20:00
 */
public class PolandNotaion {
    public static void main(String[] args) {
        //完成中缀表达式转后缀表达式
        //  1+((2+3)x4)-5 转成 1 2 3 + 4 x + 5 -
        String experssion = "1+((2+3)*4)-5";
        List<String> strings = toInfixExpressionList(experssion);
        System.out.println("中缀表达式" + strings);
        List<String> strings1 = convertPostfixExpressionList(strings);
        System.out.println("后缀表达式" + strings1);
        int cal = cal(strings1);
        System.out.println("运算结果："+cal);


        //定义一个逆波兰表达式
        //(3+4)X5-6
        //为了方便，使用空格隔开
        String suffixExpression = "3 4 + 5 * 6 -";
        List<String> list = getListString(suffixExpression);
        System.out.println(list);
        int res = cal(list);
        System.out.println("计算的结果是：" + res);
    }

    /**
     * 将中缀表达式转化到list中
     *
     * @param s 传进来的中缀表达式字符串
     * @return 封装的集合
     */
    public static List<String> toInfixExpressionList(String s) {
        //定义一个list存放中缀表达式
        ArrayList<String> list = new ArrayList<>();
        int i = 0;//指针,用于遍历字符串
        String str;//对多位数的拼接
        char c; //每遍历到一个字符就放入
        do {
            //如果c是非数字,就加入到list
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                //不是数字
                list.add("" + c);
                i++;
            } else {
                //如果是数字 需要考虑多位数
                str = "";//置空
                //如果是数字，并且还未遍历到最后,就进行字符串拼接
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    /**
     * 将中缀表达式解析成逆波兰后缀表达式
     *
     * @param list 表达式
     * @return 逆波兰表达式
     */
    public static List<String> convertPostfixExpressionList(List<String> list) {
        //定义两个栈 由于第二个数栈在整个过程中没有pop操作，所以直接用list替换数栈
        Stack<String> s1 = new Stack<>();//符号栈
        ArrayList<String> s2 = new ArrayList<>();//数集

        //遍历传进来的表达式集
        for (String item : list) {
            //如果是一个数，就入数栈
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //如果还没有到 ） 那么就继续弹出到数栈
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将 ) 弹出
            } else {
                //当入栈的运算符优先级小于或等于符号栈顶的运算符的优先级
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    //就将符号栈的运算符加入到数栈中
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //将s1中剩余运算符依次弹出并加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 将逆波兰表达式解析
     *
     * @param suffixExpression 表达式
     * @return 解析成的集合
     */
    public static List<String> getListString(String suffixExpression) {
        //将suffixExpression分割 根据空格分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        //遍历后放进数组
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    /**
     * 计算后缀表达式
     *
     * @param list 传进来需要计算的表达式
     * @return 计算结果
     */
    public static int cal(List<String> list) {
        //创建栈
        Stack<String> stack = new Stack<>();
        //遍历list
        for (String item : list) {
            //使用正则表达式取数据
            if (item.matches("\\d+")) {//匹配的是多位数
                //入栈
                stack.push(item);
            } else {
                //弹出两个数并运算,再将结果入栈
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res;
                if (item.equals("+")) {
                    res = num2 + num1;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                //把结果入栈
                stack.push(String.valueOf(res));
            }
        }
        //最后栈中留下的就是结果
        return Integer.parseInt(stack.pop());
    }
}

class Operation {
    private static int ADD = 1;//加
    private static int SUB = 1;//减
    private static int MUL = 2;//乘
    private static int DIV = 2;//除

    /**
     * 根据传进来的运算符返回优先级
     *
     * @param operation 运算符
     * @return 优先级
     */
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("运算符好像有误");
                break;
        }
        return result;
    }
}

